#include "Search.h"
#include <set>
#include <queue>
#include <stack>
#include <iostream>
#include <algorithm>

std::vector<int> Search::DFS(Graph& newGraph, int StartNode, int DestinationNode)
{
	Graph& TheGraph = newGraph;
	std::set<int> VistedNodes;
	std::stack<int> TheStack;
	std::map<int, int> ThePathMap;
	EdgeList CurrentNodesEdges; 
	int CurrentNode = 0;

	TheStack.push(StartNode);

	while(!TheStack.empty())
	{
		CurrentNode = TheStack.top();
		TheStack.pop();
		VistedNodes.insert(CurrentNode);
		if(CurrentNode == DestinationNode)
		{
			return CreatePath(StartNode, DestinationNode, ThePathMap);
		}
		CurrentNodesEdges = TheGraph.GetEdgeList(CurrentNode);

		for(auto it = CurrentNodesEdges.begin(); it != CurrentNodesEdges.end(); ++it)
		{
			if(VistedNodes.find(it->ReturnEndNodeID()) == VistedNodes.end())
			{
				TheStack.push(it->ReturnEndNodeID());
				ThePathMap[it->ReturnEndNodeID()] = CurrentNode;
				VistedNodes.insert(it->ReturnEndNodeID());
			}	
		}
	}
	
	std::vector<int> tempvec;
	return tempvec;
}


std::vector<int> Search::CreatePath(int start, int end, std::map<int, int> PathMap)
{
	std::vector<int> Result;
	
	int node = end;

	do
	{
		Result.push_back(node);
		node = PathMap[node];
	}
	while(node != start);

	std::reverse(Result.begin(), Result.end());

	return Result;
}

std::vector<int> Search::BFS(Graph& newGraph, int StartNode, int DestinationNode)
{
	if(StartNode == DestinationNode)
	{
		std::vector<int> tempvec;
		tempvec.push_back(StartNode);
		std::cout << "Search Failed From " << StartNode << " To " << DestinationNode << "\n";
		return tempvec;
	}
	Graph& TheGraph = newGraph;
	std::set<int> VistedNodes;
	std::queue<int> TheQueue;
	std::map<int, int> ThePathMap;
	EdgeList CurrentNodesEdges; 
	int CurrentNode = 0;

	TheQueue.push(StartNode);

	while(!TheQueue.empty())
	{
		CurrentNode = TheQueue.front();
		TheQueue.pop();
		VistedNodes.insert(CurrentNode);
		if(CurrentNode == DestinationNode)
		{
			return CreatePath(StartNode, DestinationNode, ThePathMap);
		}
		CurrentNodesEdges = TheGraph.GetEdgeList(CurrentNode);

		for(auto it = CurrentNodesEdges.begin(); it != CurrentNodesEdges.end(); ++it)
		{
			if(VistedNodes.find(it->ReturnEndNodeID()) == VistedNodes.end())
			{
				TheQueue.push(it->ReturnEndNodeID());
				ThePathMap[it->ReturnEndNodeID()] = CurrentNode;
				VistedNodes.insert(it->ReturnEndNodeID());
			}	
		}
	}
	
	std::vector<int> tempvec;
	return tempvec;
}

std::vector<int> Search::Dijkstra(Graph& newGraph, int StartNode, int DestinationNode)
{
	std::map<int, float> TheCostsMap;
	std::vector<int> ResultPath;


	return ResultPath;
}